//Given the head of a singly linked list, return true if it is a palindrome. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,2,1]
//Output: true
// 
//
// Example 2: 
//
// 
//Input: head = [1,2]
//Output: false
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [1, 10⁵]. 
// 0 <= Node.val <= 9 
// 
//
// 
//Follow up: Could you do it in O(n) time and O(1) space? Related Topics Linked 
//List Two Pointers Stack Recursion 👍 6681 👎 480


package leetcode.editor.en;

import listnode.ListNode;

public class _234_PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new _234_PalindromeLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head==null || head.next == null){
                return true;
            }
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode pre = null;
            ListNode cur = slow.next;
            while (cur != null) {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            while (pre!=null && head!=null){
                if (pre.val!=head.val) {
                    return false;
                }
                pre = pre.next;
                head = head.next;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}